# 编写一个程序，通过填充空格来解决数独问题。
#  数独的解法需 遵循如下规则：
#  数字 1-9 在每一行只能出现一次。
#  数字 1-9 在每一列只能出现一次。
#  数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
#  数独部分空格内已填入了数字，空白格用 '.' 表示。
#
#  示例：
# 输入：board = [
# ["5","3",".",".","7",".",".",".","."],
# ["6",".",".","1","9","5",".",".","."],
# [".","9","8",".",".",".",".","6","."],
# ["8",".",".",".","6",".",".",".","3"],
# ["4",".",".","8",".","3",".",".","1"],
# ["7",".",".",".","2",".",".",".","6"],
# [".","6",".",".",".",".","2","8","."],
# [".",".",".","4","1","9",".",".","5"],
# [".",".",".",".","8",".",".","7","9"]]
#
# 输出：[
# ["5","3","4","6","7","8","9","1","2"],
# ["6","7","2","1","9","5","3","4","8"],
# ["1","9","8","3","4","2","5","6","7"],
# ["8","5","9","7","6","1","4","2","3"],
# ["4","2","6","8","5","3","7","9","1"],
# ["7","1","3","9","2","4","8","5","6"],
# ["9","6","1","5","3","7","2","8","4"],
# ["2","8","7","4","1","9","6","3","5"],
# ["3","4","5","2","8","6","1","7","9"]]
from typing import List


class Solution:
    def solveSudoku2(self, board: List[List[str]]) -> None:
        """
        位运算优化(空间优化，记录状态使用的空间变得更小)
        用一维数组记录每行(列)每个数字是否出现
        用二维数组记录每个九宫格每个数字是否出现
        然后，先将所有需要填充的位置坐标记录下来
        最后就是逐个根据前面记录的行、列、九宫格的数字情况逐步进行尝试(遇到不能完成将所有空白填满的就回溯，最终得到结果)
        :param board:
        :return:
        """
        lineTags = [0] * 9  # lineTags[i] = Ob010000100 表示第 i 行已经出现过3、 8 了
        columnTags = [0] * 9  # columnTags[i] = Ob010010001 表示第 i 行已经出现过1、5、8 了
        blockTags = [[0] * 3 for _ in range(3)]  # blockTags[i][j] = Ob010010001 表示(i, j)这个九宫格已经出现过1、5、8 了
        finished = False
        spaces = []  # 记录 '.'在 board 中的坐标

        def flip(i: int, j: int, digit: int) -> None:
            lineTags[i] ^= (1 << digit)
            columnTags[j] ^= (1 << digit)
            blockTags[i // 3][j // 3] ^= (1 << digit)

        def dfs(pos: int) -> None:
            nonlocal finished
            if pos == len(spaces):
                finished = True
                return
            i, j = spaces[pos]
            mask = ~(lineTags[i] | columnTags[j] | blockTags[i // 3][j // 3]) & 0x1ff
            while mask:
                digitMask = mask & (-mask)  # mask & (-mask)得到mask二进制表示中最低位的 1
                digit = bin(digitMask).count("0") - 1
                flip(i, j, digit)
                board[i][j] = str(digit + 1)
                dfs(pos + 1)
                flip(i, j, digit)
                mask &= (mask - 1)
                if finished:
                    return

        for i in range(9):  # 遍历board初始化所有标志，得到所有需要填入的空白的坐标
            for j in range(9):
                if board[i][j] == ".":
                    spaces.append((i, j))
                else:
                    flip(i, j, int(board[i][j]) - 1)

        dfs(0)

    def solveSudoku1(self, board: List[List[str]]) -> None:
        """
        解法一:回溯
        用二维数组记录每行(列)每个数字是否出现
        用三维数组记录每个九宫格每个数字是否出现
        然后，先将所有需要填充的位置坐标记录下来
        最后就是逐个根据前面记录的行、列、九宫格的数字情况逐步进行尝试(遇到不能完成将所有空白填满的就回溯，最终得到结果)
        :param board:
        :return:
        """
        finished = False
        lineFlags = [[False] * 9 for _ in range(9)]  # linesFlag[i][j] = True 表示第 i 行已经出现过 j + 1 这个数字
        columnFlags = [[False] * 9 for _ in range(9)]  # columnFlags[i][j] = True 表示第 i 列已经出现过 j + 1 这个数字
        # blockFlags[i][j][k] = True 表示(i, j)这个九宫格已经出现过 k+ 1这个数字
        blockFlags = [[[False] * 9 for __ in range(3)] for _ in range(3)]
        spacePoss = []  # 记录 '.'在 board 中的坐标

        def backTrace(pos: int) -> None:
            nonlocal finished
            if pos == len(spacePoss):
                finished = True
                return
            x, y = spacePoss[pos]
            for num in range(9):  # 在 board[i][j] 上依次尝试所有可能的数
                if lineFlags[x][num] == columnFlags[y][num] == blockFlags[x // 3][y // 3][num] is False:
                    lineFlags[x][num] = columnFlags[y][num] = blockFlags[x // 3][y // 3][num] = True
                    board[x][y] = str(num + 1)
                    pos += 1
                    backTrace(pos)  # 找下一个位置继续尝试
                    pos -= 1
                    board[x][y] = str(num + 1)
                    lineFlags[x][num] = columnFlags[y][num] = blockFlags[x // 3][y // 3][num] = False
                if finished:
                    return

        for i in range(9):  # 遍历board初始化所有标志，得到所有需要填入的空白的坐标
            for j in range(9):
                if board[i][j] == '.':
                    spacePoss.append((i, j))
                else:
                    tmpNum = int(board[i][j]) - 1
                    lineFlags[i][tmpNum] = True
                    columnFlags[j][tmpNum] = True
                    blockFlags[i // 3][j // 3][tmpNum] = True

        backTrace(0)

    def solveSudoku(self, board: List[List[str]]) -> None:
        self.solveSudoku1(board)


if __name__ == "__main__":
    board = [
        ["5", "3", ".", ".", "7", ".", ".", ".", "."],
        ["6", ".", ".", "1", "9", "5", ".", ".", "."],
        [".", "9", "8", ".", ".", ".", ".", "6", "."],
        ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
        ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
        ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
        [".", "6", ".", ".", ".", ".", "2", "8", "."],
        [".", ".", ".", "4", "1", "9", ".", ".", "5"],
        [".", ".", ".", ".", "8", ".", ".", "7", "9"]]
    Solution().solveSudoku(board)
    for line in board:
        print(line)
